package leetcode101.greedy_strategy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code6
 * @Description A string S of lowercase English letters is given.
 * We want to partition this string into as many parts as possible so that each letter appears in at most one part,
 * and return a list of integers representing the size of these parts.
 * Example 1:
 *
 * Input: S = "ababcbacadefegdehijhklij"
 * Output: [9,7,8]
 * Explanation:
 * The partition is "ababcbaca", "defegde", "hijhklij".
 * This is a partition so that each letter appears in at most one part.
 * A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
 *
 * Note:
 *
 * S will have length in range [1, 500].
 * S will consist of lowercase English letters ('a' to 'z') only.
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-23 10:17
 */
public class Code6 {

    public static void main(String[] args) {
//        partitionLabels("ababcbacadefegdehijhklij");
//        partitionLabels("abcaabdeefgehehikhi");
        partitionLabels("aedbdedda");
    }

    public static List<Integer> partitionLabels(String S) {
        /*
         1. find every char's last index
         There is a little tips:
         Use HashMap to store ever char's index of the last occurrence;
         */
        HashMap<Character, Integer> lastIndex = new HashMap<>();
        for (int i = 0; i < S.length(); i++) {
            lastIndex.put(S.charAt(i), i);
        }

        List<Integer> res = new ArrayList<>();

        int start = 0, end = 0;
        for (int i = 0; i < S.length(); i++) {
            end = Math.max(end, lastIndex.get(S.charAt(i)));
            if (i == end) {
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
}
/*
这道题学会了用双指针法去定义每一个区间的长度。
 */